package cn.szv5.leetcode;

/**
 * @author carlz@rinsys.com
 * @date 2022/3/30 11:42
 */
public class NumberOfRecentCalls933 {

    public static void main(String[] args) {
        RecentCounter solution = new NumberOfRecentCalls933().new RecentCounter();
        int[] arr = {1, 100, 3001, 3002};
        for (int i = 0; i < arr.length; i++) {
            System.out.println(solution.ping(arr[i]));
        }
        System.out.println();
    }

    class RecentCounter {

        Queue q;

        public RecentCounter() {
            q = new Queue();
        }

        /**
         * 最优解：队列解法
         * 1.使用链表实现一个队列
         * 定义属性：队头-head、队尾-tail、长度-size
         * 定义方法：添加节点-add(int)、移除节点-poll() 、队列长度-size()
         * 定义内部类：Node，封装每次入队的请求数据和指向下一个节点的指针
         * 2.每次请求向队列尾部追加节点
         * 3.循环检查队头数据是否合法
         * 不合法则移除该节点
         * 4.返回队列长度
         *
         * @param t
         * @return
         */
        public int ping(int t) {
            q.add(t);
            while (q.head.getVal() < t - 3000) {
                q.poll();
            }
            return q.size;
        }

        class Queue {
            Node head;
            Node tail;
            int size = 0;

            /**
             * 向队尾添加一个节点
             *
             * @param x
             */
            public void add(int x) {
                Node last = tail;
                Node newNode = new Node(x);
                tail = newNode;
                //第一次添加数据
                if (last == null) {
                    head = newNode;
                    tail = newNode;
                } else {
                    // 前一个节点指向新节点
                    last.next = newNode;
                }
                // 每添加一个节点，队列长度+1
                size++;
            }

            /**
             * 从头部移除一个节点
             *
             * @return
             */
            public int poll() {
                // 获取头节点的数据
                int headVal = head.val;
                Node next = head.next;
                // 链表第一个节点断开
                head.next = null;
                // head指针指向后一个节点
                head = next;
                if (next == null) {
                    tail = null;
                }
                size--;
                return headVal;
            }

            public int size() {
                return size;
            }

            /**
             * 队列节点：链表结构
             */
            class Node {
                int val;
                Node next;

                Node(int x) {
                    val = x;
                }

                int getVal() {
                    return val;
                }
            }
        }
    }
}
